package com.leetcode;

import java.util.ArrayList;
import java.util.List;

/**
 * TODO
 *
 * @author lefly
 * @version 1.0
 * @classname No93
 * @description 93. 复原IP地址
 * @date 2021/1/27 下午2:15
 */
public class No93 {
    public static void main(String[] args) {
        String s = "25525511135";
        List<String> res = restoreIpAddresses(s);
        for (int i = 0; i < res.size(); i++) {
            System.out.println(res.get(i));
        }
    }

    public static List<String> restoreIpAddresses(String s) {
        List<String> res = new ArrayList<>();
        if(s == null || s == "" || s.length() < 1){
            return res;
        }
        StringBuilder str = new StringBuilder();
        getAddress(s,res,str,0);

        return res;
    }

    private static void getAddress(String s,List<String> res,StringBuilder tempIP,int point){
        // 全部用完且小数点正好为3个
        if(s.length() == 0 || point == 4){
            if(s.length() == 0 && point == 4){
                res.add(tempIP.toString());
                return;
            }
            return;
        }
        // 截取（1-3位）
        for (int i = 0; i < s.length() && i < 3; i++) {
            // 前导不能是0
            if(i > 0 && s.charAt(0) == '0'){
                break;
            }
            String part = s.substring(0,i + 1);
            if(Integer.parseInt(part) <= 255){
                // 不是第一个
                if(tempIP.length() > 0){
                    part = "." + part;
                }
                tempIP.append(part);
                getAddress(s.substring(i + 1),res,tempIP,point + 1);
                tempIP.delete(tempIP.length() - part.length(),tempIP.length());
            }

        }
    }

}
